package java.util;

public class Arrays {

	private Arrays() {
	}

	/**
	 * Perform a binary search of a byte array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(byte[] a, byte key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a byte array for a key. The range
	 * must be sorted (as by the <code>sort(byte[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(byte[] a, int low, int hi, byte key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final byte d = a[mid];
			if (d == key)
				return mid;
			else if (d > key)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop.
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of a char array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(char[] a, char key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a char array for a key. The range
	 * must be sorted (as by the <code>sort(char[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(char[] a, int low, int hi, char key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final char d = a[mid];
			if (d == key)
				return mid;
			else if (d > key)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop.
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of a short array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(short[] a, short key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a short array for a key. The range
	 * must be sorted (as by the <code>sort(short[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(short[] a, int low, int hi, short key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final short d = a[mid];
			if (d == key)
				return mid;
			else if (d > key)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop.
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of an int array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(int[] a, int key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of an integer array for a key. The
	 * range must be sorted (as by the <code>sort(int[], int, int)</code>
	 * method) - if it is not, the behaviour of this method is undefined, and
	 * may be an infinite loop. If the array contains the key more than once,
	 * any one of them may be found. Note: although the specification allows for
	 * an infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(int[] a, int low, int hi, int key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final int d = a[mid];
			if (d == key)
				return mid;
			else if (d > key)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop.
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of a long array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(long[] a, long key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a long array for a key. The range
	 * must be sorted (as by the <code>sort(long[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(long[] a, int low, int hi, long key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final long d = a[mid];
			if (d == key)
				return mid;
			else if (d > key)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop.
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of a float array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(float[] a, float key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a float array for a key. The range
	 * must be sorted (as by the <code>sort(float[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(float[] a, int low, int hi, float key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		// Must use Float.compare to take into account NaN, +-0.
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final int r = Float.compare(a[mid], key);
			if (r == 0)
				return mid;
			else if (r > 0)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of a double array for a key. The array must be
	 * sorted (as by the sort() method) - if it is not, the behaviour of this
	 * method is undefined, and may be an infinite loop. If the array contains
	 * the key more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(double[] a, double key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key);
	}

	/**
	 * Perform a binary search of a range of a double array for a key. The range
	 * must be sorted (as by the <code>sort(double[], int, int)</code> method) -
	 * if it is not, the behaviour of this method is undefined, and may be an
	 * infinite loop. If the array contains the key more than once, any one of
	 * them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static int binarySearch(double[] a, int low, int hi, double key) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		// Must use Double.compare to take into account NaN, +-0.
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			final int r = Double.compare(a[mid], key);
			if (r == 0)
				return mid;
			else if (r > 0)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop
				low = ++mid;
		}
		return -mid - 1;
	}

	/**
	 * Perform a binary search of an Object array for a key, using the natural
	 * ordering of the elements. The array must be sorted (as by the sort()
	 * method) - if it is not, the behaviour of this method is undefined, and
	 * may be an infinite loop. Further, the key must be comparable with every
	 * item in the array. If the array contains the key more than once, any one
	 * of them may be found. Note: although the specification allows for an
	 * infinite loop if the array is unsorted, it will not happen in this (JCL)
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws ClassCastException
	 *             if key could not be compared with one of the elements of a
	 * @throws NullPointerException
	 *             if a null element in a is compared
	 */
	public static int binarySearch(Object[] a, Object key) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, key, null);
	}

	/**
	 * Perform a binary search of a range of an Object array for a key. The
	 * range must be sorted (as by the <code>sort(Object[], int, int)</code>
	 * method) - if it is not, the behaviour of this method is undefined, and
	 * may be an infinite loop. If the array contains the key more than once,
	 * any one of them may be found. Note: although the specification allows for
	 * an infinite loop if the array is unsorted, it will not happen in this
	 * implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 */
	public static int binarySearch(Object[] a, int low, int hi, Object key) {
		return binarySearch(a, low, hi, key, null);
	}

	/**
	 * Perform a binary search of an Object array for a key, using a supplied
	 * Comparator. The array must be sorted (as by the sort() method with the
	 * same Comparator) - if it is not, the behaviour of this method is
	 * undefined, and may be an infinite loop. Further, the key must be
	 * comparable with every item in the array. If the array contains the key
	 * more than once, any one of them may be found. Note: although the
	 * specification allows for an infinite loop if the array is unsorted, it
	 * will not happen in this (JCL) implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param key
	 *            the value to search for
	 * @param c
	 *            the comparator by which the array is sorted; or null to use
	 *            the elements' natural order
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws ClassCastException
	 *             if key could not be compared with one of the elements of a
	 * @throws NullPointerException
	 *             if a null element is compared with natural ordering (only
	 *             possible when c is null)
	 */
	public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
		if (a.length == 0)
			return -1;
		return binarySearch(a, 0, a.length - 1, key, c);
	}

	/**
	 * Perform a binary search of a range of an Object array for a key using a
	 * {@link Comparator}. The range must be sorted (as by the
	 * <code>sort(Object[], int, int)</code> method) - if it is not, the
	 * behaviour of this method is undefined, and may be an infinite loop. If
	 * the array contains the key more than once, any one of them may be found.
	 * Note: although the specification allows for an infinite loop if the array
	 * is unsorted, it will not happen in this implementation.
	 * 
	 * @param a
	 *            the array to search (must be sorted)
	 * @param low
	 *            the lowest index to search from.
	 * @param hi
	 *            the highest index to search to.
	 * @param key
	 *            the value to search for
	 * @param c
	 *            the comparator by which the array is sorted; or null to use
	 *            the elements' natural order
	 * @return the index at which the key was found, or -n-1 if it was not
	 *         found, where n is the index of the first value higher than key or
	 *         a.length if there is no such value.
	 * @throws ClassCastException
	 *             if key could not be compared with one of the elements of a
	 * @throws IllegalArgumentException
	 *             if <code>low > hi</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>low < 0</code> or <code>hi > a.length</code>.
	 */
	public static <T> int binarySearch(T[] a, int low, int hi, T key,
			Comparator<? super T> c) {
		if (low > hi)
			throw new IllegalArgumentException(
					"The start index is higher than " + "the finish index.");
		if (low < 0 || hi > a.length)
			throw new ArrayIndexOutOfBoundsException(
					"One of the indices is out " + "of bounds.");
		int mid = 0;
		while (low <= hi) {
			mid = (low + hi) >>> 1;
			// NOTE: Please keep the order of a[mid] and key. Although
			// not required by the specs, the RI has it in this order as
			// well, and real programs (erroneously) depend on it.
			final int d = Collections.compare(a[mid], key, c);
			if (d == 0)
				return mid;
			else if (d > 0)
				hi = mid - 1;
			else
				// This gets the insertion point right on the last loop
				low = ++mid;
		}
		return -mid - 1;
	}

	// equals
	/**
	 * Compare two boolean arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(boolean[] a1, boolean[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two byte arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(byte[] a1, byte[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two char arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(char[] a1, char[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two short arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(short[] a1, short[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two int arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(int[] a1, int[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two long arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(long[] a1, long[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (a1[i] != a2[i])
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two float arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(float[] a1, float[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// Must use Float.compare to take into account NaN, +-0.
		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (Float.compare(a1[i], a2[i]) != 0)
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two double arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a2 is of the same length
	 *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
	 */
	public static boolean equals(double[] a1, double[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// Must use Double.compare to take into account NaN, +-0.
		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (Double.compare(a1[i], a2[i]) != 0)
					return false;
			return true;
		}
		return false;
	}

	/**
	 * Compare two Object arrays for equality.
	 * 
	 * @param a1
	 *            the first array to compare
	 * @param a2
	 *            the second array to compare
	 * @return true if a1 and a2 are both null, or if a1 is of the same length
	 *         as a2, and for each 0 <= i < a.length, a1[i] == null ? a2[i] ==
	 *         null : a1[i].equals(a2[i]).
	 */
	public static boolean equals(Object[] a1, Object[] a2) {
		// Quick test which saves comparing elements of the same array, and also
		// catches the case that both are null.
		if (a1 == a2)
			return true;

		if (null == a1 || null == a2)
			return false;

		// If they're the same length, test each element
		if (a1.length == a2.length) {
			int i = a1.length;
			while (--i >= 0)
				if (!AbstractCollection.equals(a1[i], a2[i]))
					return false;
			return true;
		}
		return false;
	}

	// fill
	/**
	 * Fill an array with a boolean value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(boolean[] a, boolean val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a boolean value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a byte value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(byte[] a, byte val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a byte value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a char value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(char[] a, char val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a char value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(char[] a, int fromIndex, int toIndex, char val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a short value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(short[] a, short val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a short value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(short[] a, int fromIndex, int toIndex, short val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with an int value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(int[] a, int val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with an int value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(int[] a, int fromIndex, int toIndex, int val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a long value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(long[] a, long val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a long value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(long[] a, int fromIndex, int toIndex, long val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a float value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(float[] a, float val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a float value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(float[] a, int fromIndex, int toIndex, float val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with a double value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 */
	public static void fill(double[] a, double val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with a double value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(double[] a, int fromIndex, int toIndex, double val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	/**
	 * Fill an array with an Object value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param val
	 *            the value to fill it with
	 * @throws ClassCastException
	 *             if val is not an instance of the element type of a.
	 */
	public static void fill(Object[] a, Object val) {
		fill(a, 0, a.length, val);
	}

	/**
	 * Fill a range of an array with an Object value.
	 * 
	 * @param a
	 *            the array to fill
	 * @param fromIndex
	 *            the index to fill from, inclusive
	 * @param toIndex
	 *            the index to fill to, exclusive
	 * @param val
	 *            the value to fill with
	 * @throws ClassCastException
	 *             if val is not an instance of the element type of a.
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}

	// sort
	// Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm
	// as specified by Sun and porting it to Java. The algorithm is an optimised
	// quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
	// "Engineering a Sort Function", Software-Practice and Experience, Vol.
	// 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
	// performance on many arrays that would take quadratic time with a standard
	// quicksort.

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the byte array to sort
	 */
	public static void sort(byte[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the byte array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(byte[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, byte[] d) {
		return (d[a] < d[b] ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
				: (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, byte[] a) {
		byte c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, byte[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(byte[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from && array[j - 1] > array[j]; j--)
					swap(j, j - 1, array);
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = array[b] - array[from]) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = array[c] - array[from]) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the char array to sort
	 */
	public static void sort(char[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the char array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(char[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, char[] d) {
		return (d[a] < d[b] ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
				: (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, char[] a) {
		char c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, char[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(char[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from && array[j - 1] > array[j]; j--)
					swap(j, j - 1, array);
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = array[b] - array[from]) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = array[c] - array[from]) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the short array to sort
	 */
	public static void sort(short[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the short array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(short[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, short[] d) {
		return (d[a] < d[b] ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
				: (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, short[] a) {
		short c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, short[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(short[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from && array[j - 1] > array[j]; j--)
					swap(j, j - 1, array);
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = array[b] - array[from]) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = array[c] - array[from]) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the int array to sort
	 */
	public static void sort(int[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the int array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(int[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, int[] d) {
		return (d[a] < d[b] ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
				: (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, int[] a) {
		int c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, int[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Compares two integers in natural order, since a - b is inadequate.
	 * 
	 * @param a
	 *            the first int
	 * @param b
	 *            the second int
	 * @return &lt; 0, 0, or &gt; 0 accorting to the comparison
	 */
	private static int compare(int a, int b) {
		return a < b ? -1 : a == b ? 0 : 1;
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(int[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from && array[j - 1] > array[j]; j--)
					swap(j, j - 1, array);
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = compare(array[b], array[from])) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = compare(array[c], array[from])) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the long array to sort
	 */
	public static void sort(long[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the long array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(long[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, long[] d) {
		return (d[a] < d[b] ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
				: (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, long[] a) {
		long c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, long[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Compares two longs in natural order, since a - b is inadequate.
	 * 
	 * @param a
	 *            the first long
	 * @param b
	 *            the second long
	 * @return &lt; 0, 0, or &gt; 0 accorting to the comparison
	 */
	private static int compare(long a, long b) {
		return a < b ? -1 : a == b ? 0 : 1;
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(long[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from && array[j - 1] > array[j]; j--)
					swap(j, j - 1, array);
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = compare(array[b], array[from])) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = compare(array[c], array[from])) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the float array to sort
	 */
	public static void sort(float[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the float array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(float[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, float[] d) {
		return (Float.compare(d[a], d[b]) < 0 ? (Float.compare(d[b], d[c]) < 0 ? b
				: Float.compare(d[a], d[c]) < 0 ? c : a)
				: (Float.compare(d[b], d[c]) > 0 ? b : Float
						.compare(d[a], d[c]) > 0 ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, float[] a) {
		float c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, float[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(float[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from
						&& Float.compare(array[j - 1], array[j]) > 0; j--) {
					swap(j, j - 1, array);
				}
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the double array to sort
	 */
	public static void sort(double[] a) {
		qsort(a, 0, a.length);
	}

	/**
	 * Performs a stable sort on the elements, arranging them according to their
	 * natural order.
	 * 
	 * @param a
	 *            the double array to sort
	 * @param fromIndex
	 *            the first index to sort (inclusive)
	 * @param toIndex
	 *            the last index to sort (exclusive)
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex &lt; 0 || toIndex &gt; a.length
	 */
	public static void sort(double[] a, int fromIndex, int toIndex) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException();
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();
		qsort(a, fromIndex, toIndex - fromIndex);
	}

	/**
	 * Finds the index of the median of three array elements.
	 * 
	 * @param a
	 *            the first index
	 * @param b
	 *            the second index
	 * @param c
	 *            the third index
	 * @param d
	 *            the array
	 * @return the index (a, b, or c) which has the middle value of the three
	 */
	private static int med3(int a, int b, int c, double[] d) {
		return (Double.compare(d[a], d[b]) < 0 ? (Double.compare(d[b], d[c]) < 0 ? b
				: Double.compare(d[a], d[c]) < 0 ? c : a)
				: (Double.compare(d[b], d[c]) > 0 ? b : Double.compare(d[a],
						d[c]) > 0 ? c : a));
	}

	/**
	 * Swaps the elements at two locations of an array
	 * 
	 * @param i
	 *            the first index
	 * @param j
	 *            the second index
	 * @param a
	 *            the array
	 */
	private static void swap(int i, int j, double[] a) {
		double c = a[i];
		a[i] = a[j];
		a[j] = c;
	}

	/**
	 * Swaps two ranges of an array.
	 * 
	 * @param i
	 *            the first range start
	 * @param j
	 *            the second range start
	 * @param n
	 *            the element count
	 * @param a
	 *            the array
	 */
	private static void vecswap(int i, int j, int n, double[] a) {
		for (; n > 0; i++, j++, n--)
			swap(i, j, a);
	}

	/**
	 * Performs a recursive modified quicksort.
	 * 
	 * @param array
	 *            the array to sort
	 * @param from
	 *            the start index (inclusive)
	 * @param count
	 *            the number of elements to sort
	 */
	private static void qsort(double[] array, int from, int count) {
		// Use an insertion sort on small arrays.
		if (count <= 7) {
			for (int i = from + 1; i < from + count; i++)
				for (int j = i; j > from
						&& Double.compare(array[j - 1], array[j]) > 0; j--) {
					swap(j, j - 1, array);
				}
			return;
		}

		// Determine a good median element.
		int mid = from + count / 2;
		int lo = from;
		int hi = from + count - 1;

		if (count > 40) { // big arrays, pseudomedian of 9
			int s = count / 8;
			lo = med3(lo, lo + s, lo + 2 * s, array);
			mid = med3(mid - s, mid, mid + s, array);
			hi = med3(hi - 2 * s, hi - s, hi, array);
		}
		mid = med3(lo, mid, hi, array);

		int a, b, c, d;
		int comp;

		// Pull the median element out of the fray, and use it as a pivot.
		swap(from, mid, array);
		a = b = from;
		c = d = from + count - 1;

		// Repeatedly move b and c to each other, swapping elements so
		// that all elements before index b are less than the pivot, and all
		// elements after index c are greater than the pivot. a and b track
		// the elements equal to the pivot.
		while (true) {
			while (b <= c
					&& (comp = Double.compare(array[b], array[from])) <= 0) {
				if (comp == 0) {
					swap(a, b, array);
					a++;
				}
				b++;
			}
			while (c >= b
					&& (comp = Double.compare(array[c], array[from])) >= 0) {
				if (comp == 0) {
					swap(c, d, array);
					d--;
				}
				c--;
			}
			if (b > c)
				break;
			swap(b, c, array);
			b++;
			c--;
		}

		// Swap pivot(s) back in place, the recurse on left and right sections.
		hi = from + count;
		int span;
		span = Math.min(a - from, b - a);
		vecswap(from, b - span, span, array);

		span = Math.min(d - c, hi - d - 1);
		vecswap(b, hi - span, span, array);

		span = b - a;
		if (span > 1)
			qsort(array, from, span);

		span = d - c;
		if (span > 1)
			qsort(array, hi - span, span);
	}

	/**
	 * Sort an array of Objects according to their natural ordering. The sort is
	 * guaranteed to be stable, that is, equal elements will not be reordered.
	 * The sort algorithm is a mergesort with the merge omitted if the last
	 * element of one half comes before the first element of the other half.
	 * This algorithm gives guaranteed O(n*log(n)) time, at the expense of
	 * making a copy of the array.
	 * 
	 * @param a
	 *            the array to be sorted
	 * @throws ClassCastException
	 *             if any two elements are not mutually comparable
	 * @throws NullPointerException
	 *             if an element is null (since null.compareTo cannot work)
	 * @see Comparable
	 */
	public static void sort(Object[] a) {
		sort(a, 0, a.length, null);
	}

	/**
	 * Sort an array of Objects according to a Comparator. The sort is
	 * guaranteed to be stable, that is, equal elements will not be reordered.
	 * The sort algorithm is a mergesort with the merge omitted if the last
	 * element of one half comes before the first element of the other half.
	 * This algorithm gives guaranteed O(n*log(n)) time, at the expense of
	 * making a copy of the array.
	 * 
	 * @param a
	 *            the array to be sorted
	 * @param c
	 *            a Comparator to use in sorting the array; or null to indicate
	 *            the elements' natural order
	 * @throws ClassCastException
	 *             if any two elements are not mutually comparable by the
	 *             Comparator provided
	 * @throws NullPointerException
	 *             if a null element is compared with natural ordering (only
	 *             possible when c is null)
	 */
	public static <T> void sort(T[] a, Comparator<? super T> c) {
		sort(a, 0, a.length, c);
	}

	/**
	 * Sort an array of Objects according to their natural ordering. The sort is
	 * guaranteed to be stable, that is, equal elements will not be reordered.
	 * The sort algorithm is a mergesort with the merge omitted if the last
	 * element of one half comes before the first element of the other half.
	 * This algorithm gives guaranteed O(n*log(n)) time, at the expense of
	 * making a copy of the array.
	 * 
	 * @param a
	 *            the array to be sorted
	 * @param fromIndex
	 *            the index of the first element to be sorted
	 * @param toIndex
	 *            the index of the last element to be sorted plus one
	 * @throws ClassCastException
	 *             if any two elements are not mutually comparable
	 * @throws NullPointerException
	 *             if an element is null (since null.compareTo cannot work)
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex and toIndex are not in range.
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 */
	public static void sort(Object[] a, int fromIndex, int toIndex) {
		sort(a, fromIndex, toIndex, null);
	}

	/**
	 * Sort an array of Objects according to a Comparator. The sort is
	 * guaranteed to be stable, that is, equal elements will not be reordered.
	 * The sort algorithm is a mergesort with the merge omitted if the last
	 * element of one half comes before the first element of the other half.
	 * This algorithm gives guaranteed O(n*log(n)) time, at the expense of
	 * making a copy of the array.
	 * 
	 * @param a
	 *            the array to be sorted
	 * @param fromIndex
	 *            the index of the first element to be sorted
	 * @param toIndex
	 *            the index of the last element to be sorted plus one
	 * @param c
	 *            a Comparator to use in sorting the array; or null to indicate
	 *            the elements' natural order
	 * @throws ClassCastException
	 *             if any two elements are not mutually comparable by the
	 *             Comparator provided
	 * @throws ArrayIndexOutOfBoundsException
	 *             if fromIndex and toIndex are not in range.
	 * @throws IllegalArgumentException
	 *             if fromIndex &gt; toIndex
	 * @throws NullPointerException
	 *             if a null element is compared with natural ordering (only
	 *             possible when c is null)
	 */
	public static <T> void sort(T[] a, int fromIndex, int toIndex,
			Comparator<? super T> c) {
		if (fromIndex > toIndex)
			throw new IllegalArgumentException("fromIndex " + fromIndex
					+ " > toIndex " + toIndex);
		if (fromIndex < 0)
			throw new ArrayIndexOutOfBoundsException();

		// In general, the code attempts to be simple rather than fast, the
		// idea being that a good optimising JIT will be able to optimise it
		// better than I can, and if I try it will make it more confusing for
		// the JIT. First presort the array in chunks of length 6 with insertion
		// sort. A mergesort would give too much overhead for this length.
		for (int chunk = fromIndex; chunk < toIndex; chunk += 6) {
			int end = Math.min(chunk + 6, toIndex);
			for (int i = chunk + 1; i < end; i++) {
				if (Collections.compare(a[i - 1], a[i], c) > 0) {
					// not already sorted
					int j = i;
					T elem = a[j];
					do {
						a[j] = a[j - 1];
						j--;
					} while (j > chunk
							&& Collections.compare(a[j - 1], elem, c) > 0);
					a[j] = elem;
				}
			}
		}

		int len = toIndex - fromIndex;
		// If length is smaller or equal 6 we are done.
		if (len <= 6)
			return;

		T[] src = a;
		T[] dest = (T[]) new Object[len];
		T[] t = null; // t is used for swapping src and dest

		// The difference of the fromIndex of the src and dest array.
		int srcDestDiff = -fromIndex;

		// The merges are done in this loop
		for (int size = 6; size < len; size <<= 1) {
			for (int start = fromIndex; start < toIndex; start += size << 1) {
				// mid is the start of the second sublist;
				// end the start of the next sublist (or end of array).
				int mid = start + size;
				int end = Math.min(toIndex, mid + size);

				// The second list is empty or the elements are already in
				// order - no need to merge
				if (mid >= end
						|| Collections.compare(src[mid - 1], src[mid], c) <= 0) {
					System.arraycopy(src, start, dest, start + srcDestDiff, end
							- start);

					// The two halves just need swapping - no need to merge
				} else if (Collections.compare(src[start], src[end - 1], c) > 0) {
					System.arraycopy(src, start, dest,
							end - size + srcDestDiff, size);
					System.arraycopy(src, mid, dest, start + srcDestDiff, end
							- mid);

				} else {
					// Declare a lot of variables to save repeating
					// calculations. Hopefully a decent JIT will put these
					// in registers and make this fast
					int p1 = start;
					int p2 = mid;
					int i = start + srcDestDiff;

					// The main merge loop; terminates as soon as either
					// half is ended
					while (p1 < mid && p2 < end) {
						dest[i++] = src[(Collections.compare(src[p1], src[p2],
								c) <= 0 ? p1++ : p2++)];
					}

					// Finish up by copying the remainder of whichever half
					// wasn't finished.
					if (p1 < mid)
						System.arraycopy(src, p1, dest, i, mid - p1);
					else
						System.arraycopy(src, p2, dest, i, end - p2);
				}
			}
			// swap src and dest ready for the next merge
			t = src;
			src = dest;
			dest = t;
			fromIndex += srcDestDiff;
			toIndex += srcDestDiff;
			srcDestDiff = -srcDestDiff;
		}

		// make sure the result ends up back in the right place. Note
		// that src and dest may have been swapped above, so src
		// contains the sorted array.
		if (src != a) {
			// Note that fromIndex == 0.
			System.arraycopy(src, 0, a, srcDestDiff, toIndex);
		}
	}

	/**
	 * Returns a list "view" of the specified array. This method is intended to
	 * make it easy to use the Collections API with existing array-based APIs
	 * and programs. Changes in the list or the array show up in both places.
	 * The list does not support element addition or removal, but does permit
	 * value modification. The returned list implements both Serializable and
	 * RandomAccess.
	 * 
	 * @param a
	 *            the array to return a view of (<code>null</code> not
	 *            permitted)
	 * @return a fixed-size list, changes to which "write through" to the array
	 * 
	 * @throws NullPointerException
	 *             if <code>a</code> is <code>null</code>.
	 * @see Serializable
	 * @see RandomAccess
	 * @see Arrays.ArrayList
	 */
	public static <T> List<T> asList(final T... a) {
		return new Arrays.ArrayList(a);
	}

	/**
	 * Returns the hashcode of an array of long numbers. If two arrays are
	 * equal, according to <code>equals()</code>, they should have the same
	 * hashcode. The hashcode returned by the method is equal to that obtained
	 * by the corresponding <code>List</code> object. This has the same data,
	 * but represents longs in their wrapper class, <code>Long</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of long numbers for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(long[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i) {
			int elt = (int) (v[i] ^ (v[i] >>> 32));
			result = 31 * result + elt;
		}
		return result;
	}

	/**
	 * Returns the hashcode of an array of integer numbers. If two arrays are
	 * equal, according to <code>equals()</code>, they should have the same
	 * hashcode. The hashcode returned by the method is equal to that obtained
	 * by the corresponding <code>List</code> object. This has the same data,
	 * but represents ints in their wrapper class, <code>Integer</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of integer numbers for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(int[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + v[i];
		return result;
	}

	/**
	 * Returns the hashcode of an array of short numbers. If two arrays are
	 * equal, according to <code>equals()</code>, they should have the same
	 * hashcode. The hashcode returned by the method is equal to that obtained
	 * by the corresponding <code>List</code> object. This has the same data,
	 * but represents shorts in their wrapper class, <code>Short</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of short numbers for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(short[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + v[i];
		return result;
	}

	/**
	 * Returns the hashcode of an array of characters. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. This has the same data, but
	 * represents chars in their wrapper class, <code>Character</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of characters for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(char[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + v[i];
		return result;
	}

	/**
	 * Returns the hashcode of an array of bytes. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. This has the same data, but
	 * represents bytes in their wrapper class, <code>Byte</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of bytes for which the hash code should be computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(byte[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + v[i];
		return result;
	}

	/**
	 * Returns the hashcode of an array of booleans. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. This has the same data, but
	 * represents booleans in their wrapper class, <code>Boolean</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of booleans for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(boolean[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + (v[i] ? 1231 : 1237);
		return result;
	}

	/**
	 * Returns the hashcode of an array of floats. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. This has the same data, but
	 * represents floats in their wrapper class, <code>Float</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of floats for which the hash code should be computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(float[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i)
			result = 31 * result + Float.floatToIntBits(v[i]);
		return result;
	}

	/**
	 * Returns the hashcode of an array of doubles. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. This has the same data, but
	 * represents doubles in their wrapper class, <code>Double</code>. For
	 * <code>null</code>, 0 is returned.
	 * 
	 * @param v
	 *            an array of doubles for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(double[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i) {
			long l = Double.doubleToLongBits(v[i]);
			int elt = (int) (l ^ (l >>> 32));
			result = 31 * result + elt;
		}
		return result;
	}

	/**
	 * Returns the hashcode of an array of objects. If two arrays are equal,
	 * according to <code>equals()</code>, they should have the same hashcode.
	 * The hashcode returned by the method is equal to that obtained by the
	 * corresponding <code>List</code> object. For <code>null</code>, 0 is
	 * returned.
	 * 
	 * @param v
	 *            an array of integer numbers for which the hash code should be
	 *            computed.
	 * @return the hash code of the array, or 0 if null was given.
	 * @since 1.5
	 */
	public static int hashCode(Object[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i) {
			int elt = v[i] == null ? 0 : v[i].hashCode();
			result = 31 * result + elt;
		}
		return result;
	}

	public static int deepHashCode(Object[] v) {
		if (v == null)
			return 0;
		int result = 1;
		for (int i = 0; i < v.length; ++i) {
			int elt;
			if (v[i] == null)
				elt = 0;
			else if (v[i] instanceof boolean[])
				elt = hashCode((boolean[]) v[i]);
			else if (v[i] instanceof byte[])
				elt = hashCode((byte[]) v[i]);
			else if (v[i] instanceof char[])
				elt = hashCode((char[]) v[i]);
			else if (v[i] instanceof short[])
				elt = hashCode((short[]) v[i]);
			else if (v[i] instanceof int[])
				elt = hashCode((int[]) v[i]);
			else if (v[i] instanceof long[])
				elt = hashCode((long[]) v[i]);
			else if (v[i] instanceof float[])
				elt = hashCode((float[]) v[i]);
			else if (v[i] instanceof double[])
				elt = hashCode((double[]) v[i]);
			else if (v[i] instanceof Object[])
				elt = hashCode((Object[]) v[i]);
			else
				elt = v[i].hashCode();
			result = 31 * result + elt;
		}
		return result;
	}

	/** @since 1.5 */
	public static boolean deepEquals(Object[] v1, Object[] v2) {
		if (v1 == null)
			return v2 == null;
		if (v2 == null || v1.length != v2.length)
			return false;

		for (int i = 0; i < v1.length; ++i) {
			Object e1 = v1[i];
			Object e2 = v2[i];

			if (e1 == e2)
				continue;
			if (e1 == null || e2 == null)
				return false;

			boolean check;
			if (e1 instanceof boolean[] && e2 instanceof boolean[])
				check = equals((boolean[]) e1, (boolean[]) e2);
			else if (e1 instanceof byte[] && e2 instanceof byte[])
				check = equals((byte[]) e1, (byte[]) e2);
			else if (e1 instanceof char[] && e2 instanceof char[])
				check = equals((char[]) e1, (char[]) e2);
			else if (e1 instanceof short[] && e2 instanceof short[])
				check = equals((short[]) e1, (short[]) e2);
			else if (e1 instanceof int[] && e2 instanceof int[])
				check = equals((int[]) e1, (int[]) e2);
			else if (e1 instanceof long[] && e2 instanceof long[])
				check = equals((long[]) e1, (long[]) e2);
			else if (e1 instanceof float[] && e2 instanceof float[])
				check = equals((float[]) e1, (float[]) e2);
			else if (e1 instanceof double[] && e2 instanceof double[])
				check = equals((double[]) e1, (double[]) e2);
			else if (e1 instanceof Object[] && e2 instanceof Object[])
				check = equals((Object[]) e1, (Object[]) e2);
			else
				check = e1.equals(e2);
			if (!check)
				return false;
		}

		return true;
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(boolean[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(byte[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(char[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(short[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(int[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(long[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(float[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(double[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	/**
	 * Returns a String representation of the argument array. Returns "null" if
	 * <code>a</code> is null.
	 * 
	 * @param v
	 *            the array to represent
	 * @return a String representing this array
	 * @since 1.5
	 */
	public static String toString(Object[] v) {
		if (v == null)
			return "null";
		StringBuilder b = new StringBuilder("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			b.append(v[i]);
		}
		b.append("]");
		return b.toString();
	}

	private static void deepToString(Object[] v, StringBuilder b, HashSet seen) {
		b.append("[");
		for (int i = 0; i < v.length; ++i) {
			if (i > 0)
				b.append(", ");
			Object elt = v[i];
			if (elt == null)
				b.append("null");
			else if (elt instanceof boolean[])
				b.append(toString((boolean[]) elt));
			else if (elt instanceof byte[])
				b.append(toString((byte[]) elt));
			else if (elt instanceof char[])
				b.append(toString((char[]) elt));
			else if (elt instanceof short[])
				b.append(toString((short[]) elt));
			else if (elt instanceof int[])
				b.append(toString((int[]) elt));
			else if (elt instanceof long[])
				b.append(toString((long[]) elt));
			else if (elt instanceof float[])
				b.append(toString((float[]) elt));
			else if (elt instanceof double[])
				b.append(toString((double[]) elt));
			else if (elt instanceof Object[]) {
				Object[] os = (Object[]) elt;
				if (seen.contains(os))
					b.append("[...]");
				else {
					seen.add(os);
					deepToString(os, b, seen);
				}
			} else
				b.append(elt);
		}
		b.append("]");
	}

	/** @since 1.5 */
	public static String deepToString(Object[] v) {
		if (v == null)
			return "null";
		HashSet seen = new HashSet();
		StringBuilder b = new StringBuilder();
		deepToString(v, b, seen);
		return b.toString();
	}

	/**
	 * Inner class used by {@link #asList(Object[])} to provide a list interface
	 * to an array. The name, though it clashes with java.util.ArrayList, is
	 * Sun's choice for Serialization purposes. Element addition and removal is
	 * prohibited, but values can be modified.
	 * 
	 * @author Eric Blake (ebb9@email.byu.edu)
	 * @status updated to 1.4
	 */
	private static final class ArrayList<E> extends AbstractList<E> implements
			RandomAccess {

		/**
		 * The array we are viewing.
		 * 
		 * @serial the array
		 */
		private final E[] a;

		/**
		 * Construct a list view of the array.
		 * 
		 * @param a
		 *            the array to view
		 * @throws NullPointerException
		 *             if a is null
		 */
		ArrayList(E[] a) {
			// We have to explicitly check.
			if (a == null)
				throw new NullPointerException();
			this.a = a;
		}

		/**
		 * Returns the object at the specified index in the array.
		 * 
		 * @param index
		 *            The index to retrieve an object from.
		 * @return The object at the array index specified.
		 */
		public E get(int index) {
			return a[index];
		}

		/**
		 * Returns the size of the array.
		 * 
		 * @return The size.
		 */
		public int size() {
			return a.length;
		}

		/**
		 * Replaces the object at the specified index with the supplied element.
		 * 
		 * @param index
		 *            The index at which to place the new object.
		 * @param element
		 *            The new object.
		 * @return The object replaced by this operation.
		 */
		public E set(int index, E element) {
			E old = a[index];
			a[index] = element;
			return old;
		}

		/**
		 * Returns true if the array contains the supplied object.
		 * 
		 * @param o
		 *            The object to look for.
		 * @return True if the object was found.
		 */
		public boolean contains(Object o) {
			return lastIndexOf(o) >= 0;
		}

		/**
		 * Returns the first index at which the object, o, occurs in the array.
		 * 
		 * @param o
		 *            The object to search for.
		 * @return The first relevant index.
		 */
		public int indexOf(Object o) {
			int size = a.length;
			for (int i = 0; i < size; i++)
				if (ArrayList.equals(o, a[i]))
					return i;
			return -1;
		}

		/**
		 * Returns the last index at which the object, o, occurs in the array.
		 * 
		 * @param o
		 *            The object to search for.
		 * @return The last relevant index.
		 */
		public int lastIndexOf(Object o) {
			int i = a.length;
			while (--i >= 0)
				if (ArrayList.equals(o, a[i]))
					return i;
			return -1;
		}

		/**
		 * Transforms the list into an array of objects, by simplying cloning
		 * the array wrapped by this list.
		 * 
		 * @return A clone of the internal array.
		 */
		public Object[] toArray() {
			return (Object[]) a.clone();
		}

		/**
		 * Copies the objects from this list into the supplied array. The
		 * supplied array is shrunk or enlarged to the size of the internal
		 * array, and filled with its objects.
		 * 
		 * @param array
		 *            The array to fill with the objects in this list.
		 * @return The array containing the objects in this list, which may or
		 *         may not be == to array.
		 */
		public <T> T[] toArray(T[] array) {
			int size = a.length;
			if (array.length > size) {
				array[size] = null;
			}
			System.arraycopy(a, 0, array, 0, size);
			return array;
		}
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>false</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>false</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>false</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(boolean[],int,int)
	 */
	public static boolean[] copyOf(boolean[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>false</code> if <code>to</code> is greater than
	 * the length of the original array. <code>from</code> must be in the range
	 * zero to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>false</code> will be returned). The returned
	 * array is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(boolean[],int)
	 */
	public static boolean[] copyOfRange(boolean[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		boolean[] newArray = new boolean[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, false);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>(byte)0</code> to obtain the specified length. Indices that
	 * are valid for both arrays will return the same value. Indices that only
	 * exist in the returned array (due to the new length being greater than the
	 * original length) will return <code>(byte)0</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>(byte)0</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(byte[],int,int)
	 */
	public static byte[] copyOf(byte[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>(byte)0</code> if <code>to</code> is greater than
	 * the length of the original array. <code>from</code> must be in the range
	 * zero to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>(byte)0</code> will be returned). The returned
	 * array is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(byte[],int)
	 */
	public static byte[] copyOfRange(byte[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		byte[] newArray = new byte[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, (byte) 0);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>'\0'</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>'\0'</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>'\0'</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(char[],int,int)
	 */
	public static char[] copyOf(char[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>'\0'</code> if <code>to</code> is greater than
	 * the length of the original array. <code>from</code> must be in the range
	 * zero to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>'\0'</code> will be returned). The returned array
	 * is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(char[],int)
	 */
	public static char[] copyOfRange(char[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		char[] newArray = new char[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, '\0');
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>0d</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>0d</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>0d</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(double[],int,int)
	 */
	public static double[] copyOf(double[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>0d</code> if <code>to</code> is greater than the
	 * length of the original array. <code>from</code> must be in the range zero
	 * to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>0d</code> will be returned). The returned array
	 * is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(double[],int)
	 */
	public static double[] copyOfRange(double[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		double[] newArray = new double[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, 0d);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>0f</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>0f</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>0f</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(float[],int,int)
	 */
	public static float[] copyOf(float[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>0f</code> if <code>to</code> is greater than the
	 * length of the original array. <code>from</code> must be in the range zero
	 * to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>0f</code> will be returned). The returned array
	 * is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(float[],int)
	 */
	public static float[] copyOfRange(float[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		float[] newArray = new float[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, 0f);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>0</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>0</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>0</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(int[],int,int)
	 */
	public static int[] copyOf(int[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>0</code> if <code>to</code> is greater than the
	 * length of the original array. <code>from</code> must be in the range zero
	 * to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>0</code> will be returned). The returned array is
	 * always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(int[],int)
	 */
	public static int[] copyOfRange(int[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		int[] newArray = new int[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, 0);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>0L</code> to obtain the specified length. Indices that are
	 * valid for both arrays will return the same value. Indices that only exist
	 * in the returned array (due to the new length being greater than the
	 * original length) will return <code>0L</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>0L</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(long[],int,int)
	 */
	public static long[] copyOf(long[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>0L</code> if <code>to</code> is greater than the
	 * length of the original array. <code>from</code> must be in the range zero
	 * to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>0L</code> will be returned). The returned array
	 * is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(long[],int)
	 */
	public static long[] copyOfRange(long[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		long[] newArray = new long[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, 0L);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}

	/**
	 * Returns a copy of the supplied array, truncating or padding as necessary
	 * with <code>(short)0</code> to obtain the specified length. Indices that
	 * are valid for both arrays will return the same value. Indices that only
	 * exist in the returned array (due to the new length being greater than the
	 * original length) will return <code>(short)0</code>. This is equivalent to
	 * calling <code>copyOfRange(original, 0, newLength)</code>.
	 * 
	 * @param original
	 *            the original array to be copied.
	 * @param newLength
	 *            the length of the returned array.
	 * @return a copy of the original array, truncated or padded with
	 *         <code>(short)0</code> to obtain the required length.
	 * @throws NegativeArraySizeException
	 *             if <code>newLength</code> is negative.
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOfRange(short[],int,int)
	 */
	public static short[] copyOf(short[] original, int newLength) {
		if (newLength < 0)
			throw new NegativeArraySizeException("The array size is negative.");
		return copyOfRange(original, 0, newLength);
	}

	/**
	 * Copies the specified range of the supplied array to a new array, padding
	 * as necessary with <code>(short)0</code> if <code>to</code> is greater
	 * than the length of the original array. <code>from</code> must be in the
	 * range zero to <code>original.length</code> and can not be greater than
	 * <code>to</code>. The initial element of the returned array will be equal
	 * to <code>original[from]</code>, except where <code>from</code> is equal
	 * to <code>to</code> (where a zero-length array will be returned) or <code>
	 * <code>from</code> is equal to <code>original.length</code> (where an
	 * array padded with <code>(short)0</code> will be returned). The returned
	 * array is always of length <code>to - from</code>.
	 * 
	 * @param original
	 *            the array from which to copy.
	 * @param from
	 *            the initial index of the range, inclusive.
	 * @param to
	 *            the final index of the range, exclusive.
	 * @return a copy of the specified range, with padding to obtain the
	 *         required length.
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>from < 0</code> or
	 *             <code>from > original.length</code>
	 * @throws IllegalArgumentException
	 *             if <code>from > to</code>
	 * @throws NullPointerException
	 *             if <code>original</code> is <code>null</code>.
	 * @since 1.6
	 * @see #copyOf(short[],int)
	 */
	public static short[] copyOfRange(short[] original, int from, int to) {
		if (from > to)
			throw new IllegalArgumentException("The initial index is after "
					+ "the final index.");
		short[] newArray = new short[to - from];
		if (to > original.length) {
			System.arraycopy(original, from, newArray, 0, original.length
					- from);
			fill(newArray, original.length, newArray.length, (short) 0);
		} else
			System.arraycopy(original, from, newArray, 0, to - from);
		return newArray;
	}
}
